Алгоритм Гровера (также GSA от англ. Grover search algorithm) — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения

${\displaystyle (1)\qquad f(x)=1,}$

где ${\displaystyle f}$ есть булева функция от n переменных. Был предложен американским математиком Ловом Гровером в 1996 году.

Предполагается, что функция ${\displaystyle f}$ задана в виде чёрного ящика, или оракула, то есть в ходе решения можно задавать оракулу только вопрос типа: «чему равна ${\displaystyle f}$ на данном ${\displaystyle x}$?», и использовать ответ в дальнейших вычислениях. То есть, задача решения уравнения (1) является общей формой задачи перебора: здесь требуется отыскать «пароль к устройству ${\displaystyle f}$», что классически требует полного перебора всех ${\displaystyle N=2^{n}}$ вариантов.

Алгоритм Гровера находит какой-нибудь корень уравнения, используя ${\displaystyle {\frac {\pi }{4}}{\sqrt {N}}}$ обращений к функции ${\displaystyle f}$, с использованием ${\displaystyle O(n)}$ кубитов.

Смысл алгоритма Гровера состоит в «усилении амплитуды» целевого состояния за счёт убывания амплитуды всех других состояний. Геометрически алгоритм Гровера заключается во вращении текущего вектора состояния квантового компьютера по направлению точно к целевому состоянию (движение по наикратчайшему пути обеспечивает оптимальность алгоритма Гровера). Каждый шаг дает вращение на угол ${\displaystyle 2\alpha }$, где угол между ${\displaystyle I_{\tilde {0}}}$ и ${\displaystyle I_{x_{tar}}}$ составляет ${\displaystyle \pi /2-\alpha }$. Дальнейшее продолжение итераций оператора G даст продолжение обхода окружности в вещественной плоскости, порождённой данными векторами.

Гроверовское «усиление амплитуды» является, по-видимому, фундаментальным физическим феноменом в квантовой теории многих тел. Например, его учёт необходим для оценки вероятностей событий, которые кажутся «редкими». Процесс, реализующий схему алгоритма Гровера, приводит к взрывному росту первоначально пренебрежимо малой амплитуды, что способно быстро довести её до реально наблюдаемых величин.

Алгоритм Гровера также может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путём исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.